package code.oldCode.feishuSpecializedTraining.greedy;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/19
 * @description
 */
public class MyGreedy4 {
    // 860. 柠檬水找零
    public boolean lemonadeChange(int[] bills) {
        int dollar5 = 0, dollar10 = 0;
        for (int bill : bills) {
            switch (bill) {
                case 5: {
                    dollar5++;
                    continue;
                }
                case 10: {
                    if (dollar5 == 0) {
                        return false;
                    }
                    dollar10++;
                    dollar5--;
                    continue;
                }
                case 20: {
                    // 贪心：优先用10找零
                    if (dollar10 > 0 && dollar5 > 0) {
                        dollar10--;
                        dollar5--;
                    } else if (dollar5 >= 3) {
                        dollar5 -= 3;
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    // 406. 根据身高重建队列
    public int[][] reconstructQueue(int[][] people) {
        // 排序+贪心
        // 用优先队列（堆）做会更快，但是sort比较简单
        int len = people.length;
        int[][] ans = new int[len][];
        // 应该先处理矮的人，让他们先选位置，一样矮的，k大的先选；如果大的先选，矮的条件k可能不符合了
        Arrays.sort(people, (o1, o2) -> {
            if (o1[0] != o2[0])
                return o1[0] - o2[0];
            else
                return o2[1] - o1[1];
        });
        // 一个数组，存放目前没选的位置
        List<Integer> leftPos = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            leftPos.add(i);
        }
        // 遍历一遍，从小到大给出位置
        for (int[] person : people) {
            int pos = leftPos.get(person[1]);
            leftPos.remove(person[1]);
            ans[pos] = person;
        }
        return ans;
    }

    public int[][] reconstructQueue_heap(int[][] people) {
        // 排序+贪心
        // 用优先队列（堆）做会更快
        int len = people.length;
        int[][] ans = new int[len][];
        // 应该先处理矮的人，让他们先选位置，一样矮的，k大的先选；如果大的先选，矮的条件k可能不符合了
        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] != o2[0])
                return o1[0] - o2[0];
            else
                return o2[1] - o1[1];
        });
        for (int[] person : people) {
            heap.offer(person);
        }
        // 一个数组，存放目前没选的位置
        List<Integer> leftPos = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            leftPos.add(i);
        }
        // 遍历一遍，从小到大给出位置
        while (!heap.isEmpty()) {
            int[] person = heap.poll();
            int pos = leftPos.get(person[1]);
            leftPos.remove(person[1]);
            ans[pos] = person;
        }
        return ans;
    }

    // 452. 用最少数量的箭引爆气球
    public int findMinArrowShots(int[][] points) {
        // 排序+贪心
        int len = points.length;
        Arrays.sort(points, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        int nowLeft = points[0][0], nowRight = points[0][1];
        int count = 1;
        for (int i = 1; i < len; i++) {
            // 如果没交集，说明这一部分搞定了
            if (nowRight < points[i][0]) {
                count++;
                nowLeft = points[i][0];
                nowRight = points[i][1];
            }
            // 如果有交集，更新边界
            else {
                nowLeft = Math.max(nowLeft, points[i][0]);
                nowRight = Math.min(nowRight, points[i][1]);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        MyGreedy4 m = new MyGreedy4();
        System.out.println(m.findMinArrowShots(new int[][]{{-2147483646, -2147483645}, {2147483646, 2147483647}}));
    }
}
